import random
from time import *
def quick(L, R):
    """
    对数组a进行快速排序的递归调用。
    参数:
    L - 排序区间的左边界索引
    R - 排序区间的右边界索引
    全局变量:
    a - 待排序的数组
    n - 数组的长度（在此函数中未直接使用，但可能在外部影响排序行为）
    """
    # 初始化左右指针
    i, j = L, R
    # 随机选择一个基准值
    key = a[random.randint(L, R)]
    while i <= j:
        # 移动左指针直到找到需要交换的元素
        while a[i] < key:
            i += 1
        # 移动右指针直到找到需要交换的元素
        while a[j] > key:
            j -= 1
        # 交换元素，使左侧小于基准值，右侧大于基准值
        if i <= j:
            a[i], a[j] = a[j], a[i]
            i += 1
            j -= 1
    # 对左半部分进行递归排序
    if L < j:
        quick(L, j)
    # 对右半部分进行递归排序
    if i < R:
        quick(i, R)

start = time()
n = int(input())
a = list(random.randint(1, 100000) for x in range(n))
quick(0, n - 1)
#print(*a)
end = time()
print('time = ', end - start)